﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>

//int main()
//{
//	int arr[] = { 1, 1, 2 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	removeDuplicates(arr, sz);
//	return 0;
//}
//
//int removeDuplicates(int* nums, int numsSize)
//{
//	int dst = 0;
//	int prev = 0;
//	int cur = 1;
//	if (numsSize <= 1)
//	{
//		return numsSize;
//	}
//	for (; cur < numsSize; cur++, prev++)
//	{
//		if (nums[cur] != nums[prev])
//		{
//			nums[dst++] = nums[prev];
//		}
//	}
//	nums[dst++] = nums[prev];
//	return dst;
//}



//int* addToArrayForm(int* num, int numSize, int k, int* returnSize);
//
//int main()
//{
//	int arr[] = {7};
//	int k = 993;
//	int returnSize = 0;
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	addToArrayForm(arr, sz, k, &returnSize);
//	return 0;
//}
//
////
////对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1, 2, 3, 1]。
////
////给定非负整数 X 的数组形式 A，返回整数 X + K 的数组形式。
//
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize)
//{
//	int kSize = 0;
//	int kNum = k;
//	int ASize = numSize;
//	//取k的长度，例如k=1234，则kSize为4。
//	while (kNum)
//	{
//		kNum /= 10;
//		kSize++;
//	}
//	//建立新数组，将结果存入新数组retArr中
//	//数组大小为kSize与ASize中的较大值
//	int Size = (kSize > ASize ? kSize : ASize);
//	//Size + 1的目的，例如55 + 51 = 106，这样长度就大了一位
//	//为防止这样的情况则长度加一
//	int* retArr = (int*)malloc(sizeof(int)*(Size + 1));
//	int i = 0;
//	//A[]数组的下标为Ai
//	int Ai = ASize - 1;
//	int newAdd = 0;																																																																		
//	//进位符号carryNum
//	int carryNum = 0;
//	while (Size--)
//	{
//		//Asize小于kSize的情况
//		if (Ai < 0)
//		{
//			newAdd = k % 10 + carryNum;
//		}
//		else
//		{
//			//下面的情况只适用于Asize大于kSize的情况
//			//如果出现A=[1,2],k=123时，A[]数组会越界。
//			//所以就会有上面的判断情况。
//			newAdd = num[Ai] + k % 10 + carryNum;
//			Ai--;
//		}
//		//把个位去除
//		k /= 10;
//		//判断是否进位
//		if (newAdd > 9)
//		{
//			newAdd %= 10;
//			carryNum = 1;
//		}
//		else
//		{
//			carryNum = 0;
//		}
//		retArr[i] = newAdd;
//		i++;
//	}
//	//把最后的进位放进去
//	if (carryNum == 1)
//	{
//		retArr[i] = carryNum;
//		i++;
//	}
//
//	*returnSize = i;
//	//逆序输出retArr
//	int end = i;
//	int start = 0;
//	int tmp = 0;
//	for (start = 0; start < end / 2; start++)
//	{
//		tmp = retArr[start];
//		retArr[start] = retArr[end - 1 - start];
//		retArr[end - 1 - start] = tmp;
//	}
//	return retArr;
//}

//方法一：暴力求解

//void rotate(int* nums, int numsSize, int k)
//{
//	k %= numsSize;
//	int i = 0;
//	int j = 0;
//	int tmp = 0;
//	for (i = 0; i < k; i++)
//	{
//		tmp = nums[numsSize - 1];
//		for (j = numsSize - 1; j > 0; j--)
//		{
//			nums[j] = nums[j - 1];
//		}
//		nums[0] = tmp;
//	}
//
//}//时间复杂度过高


//start，end均为下标
//void Reverse(int* nums, int start, int end)
//{
//	//二分交换
//	int tmp = 0;
//	while (start < end)
//	{
//		tmp = nums[start];
//		nums[start] = nums[end];
//		nums[end] = tmp;
//		start++;
//		end--;
//	}
//}
//
//void rotate(int* nums, int numsSize, int k)
//{
//	k %= numsSize;
//	Reverse(&nums[0], 0, numsSize - 1);
//	Reverse(&nums[0], 0, k - 1);
//	Reverse(&nums[0], k, numsSize - 1);
//}
//
//int main()
//{
//	int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int k = 3;
//	rotate(arr, sz, k);
//	return 0;
//}
//
//void rotate(int* nums, int numsSize, int k)
//{
//	int i = 0;
//	k %= numsSize;
//	if (numsSize <= 1)
//		return;
//	int *retNums = (int*)malloc(sizeof(int)* 2 * numsSize);
//	for (i = 0; i < numsSize; i++)
//	{
//		retNums[i] = nums[i];
//	}
//	for (; i < numsSize * 2; i++)
//	{
//		retNums[i] = nums[i - numsSize];
//	}
//	for (i = 0; i < numsSize; i++)
//	{
//		nums[i] = retNums[numsSize - k + i];
//	}
//}
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。


struct ListNode
{
	int i;
	struct ListNode* next;
};

struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL || head->next == NULL)
		return head;
	struct ListNode* n1 = NULL;
	struct ListNode* n2 = head;
	struct ListNode* n3 = head->next;
	while (n2)
	{
		n2->next = n1;

		n1 = n2;
		n2 = n3;
		if (n3 != NULL)
		n3 = n3->next;

	}
	return n1;
}

